`
https://leetcode.cn/problems/most-beautiful-item-for-each-query/
`

/**
 * @param {number[][]} items
 * @param {number[]} queries
 * @return {number[]}
 */
var maximumBeauty = function (items, queries) {
  items.sort((a, b) => a[0] - b[0])
  // 原地计算 beauty 的前缀最大值
  for (let i = 1; i < items.length; i++) {
    items[i][1] = Math.max(items[i][1], items[i - 1][1])
  }
  return queries.map((q) => {
    // 相同 price 的 beauty 是逆序的
    // 所以找到最后一个小于等于 q 的 price 即可
    const targetIdx = lower_bound(items, q + 1, ([price]) => price) - 1
    if (targetIdx === -1) return 0
    return items[targetIdx][1]
  })
};

function lower_bound(arr, target, compareFn) {
  let left = -1, right = arr.length
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (compareFn(arr[mid]) < target) {
      left = mid
    } else {
      right = mid
    }
  }
  return right
}